import random
    
class Solution:
    def randomPartition(self, arr, low, high):
        i = random.randint(low, high)
        arr[i], arr[high] = arr[high], arr[i]
        return self.partition(arr, low, high)

    def partition(self, arr, low, high):
        x = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= arr[high]:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    def quickDivideSort(self, arr, low, high):
        n = len(arr)
        if low < high:
            pi = self.randomPartition(arr, low, high)
            self.quickDivideSort(arr, low, pi - 1)
            self.quickDivideSort(arr, pi + 1, high)

        return arr

    def quickSort(self, arr):
        low, high = 0, len(arr) - 1
        return self.quickDivideSort(arr, low, high)